package com.zhanghp.class042;

/**
 * 使用规格8和规格6的袋子买苹果问题
 * 有装下8个苹果的袋子、装下6个苹果的袋子，一定要保证买苹果时所有使用的袋子都装满
 * 对于无法装满所有袋子的方案不予考虑，给定n个苹果，返回至少要多少个袋子
 * 如果不存在每个袋子都装满的方案返回-1
 *
 * @author zhanghp
 * @since 2024/7/2 10:23
 */
public class Code01_AppleMinBags {

    public static void main(String[] args) {
        for (int i = 0; i < 100; i++) {
            System.out.println(i + " : " + bags1(i));
        }
    }

    public static int bags1(int n) {
        int ans = f(n);
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }

    public static int f(int n) {
        if (n < 0) {
            return Integer.MAX_VALUE;
        }
        if (n == 0) {
            return 0;
        }

        int ans = 0;
        int p1 = f(n - 8);
        int p2 = f(n - 6);
        // 加1的原因，是因为basecase，若为0了，则说明用了一个袋子
        p1 = p1 + (p1 == Integer.MAX_VALUE ? 0 : 1);
        p2 = p2 + (p2 == Integer.MAX_VALUE ? 0 : 1);
        return Math.min(p1, p2);
    }

    public static int bags2(int apple){

        // 6 + 8
        // 所以只有偶数才有结果，奇数没有
        if ((apple & 1) != 0) {
            return -1;
        }
        if (apple < 18) {
            if (apple == 0) {
                return 0;
            }
            if (apple == 6 || apple ==8) {
                return 1;
            }
            if (apple == 12 || apple == 14 || apple == 16) {
                return 2;
            }
            return -1;
        }
        return (apple - 18) / 8 + 3;
    }
}
